package AlgorithmTest;

public class Merge_Sort_cs50 {
	
	public int[] sort_cs50(int[] input){
		if(input.length<2) return input;
		int mid = input.length/2;
		int[] leftpart=sort_cs50(getpart(input,0,mid-1));
		int[] rightpart=sort_cs50(getpart(input,mid,input.length-1));
		return merge_cs50(leftpart,rightpart);
	}
	
	public int[] merge_cs50(int[] left,int[] right){
		int[] merged=new int[left.length+right.length];
		int mergedindex=0;
		int leftindex=0;
		int rightindex=0;
		while(mergedindex<merged.length){
			if(rightindex==right.length)
				merged[mergedindex++]=left[leftindex++];
			else if(leftindex==left.length)
				merged[mergedindex++]=right[rightindex++];
			else if(left[leftindex]<right[rightindex])
				merged[mergedindex++]=left[leftindex++];
			else
				merged[mergedindex++]=right[rightindex++];
		}
		return merged;
	}
	
	public int[] getpart(int[] input,int start,int end){
		int[] part=new int[end-start+1]; 
		for (int i = start; i <= end ; i++) {
			part[i-start]=input[i];
		}
		return part;
	}
    
    public static void main(String[] args) {
		Merge_Sort_cs50 m=new Merge_Sort_cs50();
		int[] input={3,4,5,6,7,8,9,2,1};
		int[] out=m.sort_cs50(input);
		System.out.println("s");
		for (int i = 0; i < out.length; i++) {
			System.out.print(out[i]);
		}
		System.out.println("");
		System.out.println("e");
	}
}
